package sorts;

import java.util.Arrays;
import java.util.PriorityQueue;


public class Code_215 {

    /**
     * 解法一：使用JDK自带的排序算法
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_0(int[] nums, int k) {
        if (nums == null || nums.length < 2) return nums[0];
        Arrays.sort(nums);
        int len = nums.length;
        int index = len - k;
        return nums[index];
    }

    /**
     * 解法二：使用效率很低的冒泡排序
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_1(int[] nums, int k) {
        if (nums == null || nums.length < 2) return nums[0];
        bubbleSort(nums);
        int len = nums.length;
        int index = len - k;
        return nums[index];
    }

    private void bubbleSort(int[] nums) {
        for (int i = nums.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                }
            }
        }
    }

    private void swap(int[] nums, int j, int i) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


    /**
     * 第三种解法：选择排序，时间效率任然过低
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_2(int[] nums, int k) {
        if (nums == null || nums.length < 2) return nums[0];
        selectSort(nums);
        int len = nums.length;
        int index = len - k;
        return nums[index];
    }

    private void selectSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            int minIndex = i;
            for (int j = i; j < nums.length; j++) {
                minIndex = nums[j] < nums[minIndex] ? j : minIndex;
            }
            swap(nums, i, minIndex);
        }
    }


    /**
     * 第四种解法：插入排序，同样是效率不高
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_3(int[] nums, int k) {
        if (nums == null || nums.length < 2) return nums[0];
        insertSort(nums);
        int len = nums.length;
        int index = len - k;
        return nums[index];
    }

    private void insertSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            for (int j = i - 1; j >= 0 && nums[j + 1] < nums[j]; j--) {
                swap(nums, j, j + 1);
            }
        }
    }


    /**
     * 第五种解法：随机化快速排序
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_4(int[] nums, int k) {
        if (nums == null || nums.length < 2) return nums[0];
        quickSort(nums, 0, nums.length - 1);
        int len = nums.length;
        int index = len - k;
        return nums[index];
    }

    private void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            swap(nums, left + (int) (Math.random() * (right - left + 1)), right);
            int p[] = partition(nums, left, right);
            quickSort(nums, left, p[0] - 1);
            quickSort(nums, p[1] + 1, right);
        }
    }

    private int[] partition(int[] nums, int left, int right) {
        int less = left - 1;
        int more = right;
        while (left < more) {
            if (nums[left] < nums[right]) {
                swap(nums, ++less, left++);
            } else if (nums[left] > nums[right]) {
                swap(nums, --more, left);
            } else {
                left++;
            }
        }
        swap(nums, more, right);
        return new int[]{less + 1, more};
    }


    /**
     * 第六种解法：使用大顶堆排序解决
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_5(int[] nums, int k) {
        if (nums == null || nums.length < 2) return nums[0];
        heapSort(nums);
        int len = nums.length;
        int index = len - k;
        return nums[index];
    }

    private void heapSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            heapInsert(nums, i);
        }
        int size = nums.length;
        swap(nums, 0, --size);
        while (size > 0) {
            heapify(nums, 0, size);
            swap(nums, 0, --size);
        }
    }

    private void heapify(int[] nums, int index, int size) {
        int left = index * 2 + 1;
        while (left < size) {
            int largest = left + 1 < size && nums[left + 1] > nums[left] ? left + 1 : left;
            largest = nums[largest] > nums[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(nums, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    private void heapInsert(int[] nums, int index) {
        while (nums[index] > nums[(index - 1) / 2]) {
            swap(nums, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    /**
     * 第七种解法：构造小顶堆的优先级队列实现
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_6(int[] nums, int k) {
        if (nums == null || nums.length < 2) return nums[0];
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>((a, b) -> (a - b));
        for (int i = 0; i < nums.length; i++) {
            priorityQueue.add(nums[i]);
            if (priorityQueue.size() > k) {
                priorityQueue.poll();
            }
        }
        return priorityQueue.peek();
    }


    /**
     * 第八种解法：基于快排的思想找到第K大的数
     *
     * @param nums
     * @param target
     * @return
     */
    public int findKthLargest_7(int[] nums, int target) {
        if (nums == null || nums.length < 2) return nums[0];
        int num;
        int length = nums.length;
        target = length - target;
        num = quickFind(nums, 0, nums.length - 1, target);
        return num;
    }

    public int quickFind(int[] arr, int left, int right, int target) {
        int key = arr[left];
        int l = left;
        int r = right;

        while (l < r) {
            while (l < r && arr[r] > key) r--;
            while (l < r && arr[l] <= key) l++;
            swap(arr, l, r);
        }
        arr[left] = arr[l];
        arr[l] = key;
        if (target == r) {
            return arr[r];
        } else if (target < r) {
            return quickFind(arr, left, r - 1, target);
        } else {
            return quickFind(arr, r + 1, right, target);
        }
    }

}
